/* 博弈论
    SG函数
    sg(x)表示x下一步不能到达的最小状态，即0-(x-1)的状态都是可以到达的
    mex 函数：mex(S)=min{x},(x∉S,x∈N) (不属于集合S的最小自然数)
    SG 函数：SG(x)=mex{SG(y1),SG(y2),…,SG(yk)},( yi 为 x 的后继状态(1⩽i⩽k))
    n 个有向图，起点分别为 s1,s2,…sn，则SG(s1)⨁SG(s2)⨁…⨁SG(sn)=0 时先手必败，否则必胜

    证明:
        while(a1^a2^...^an) { //只取一次使得异或结果为0
            int x = a1^a2^...^an;
            设x的最高位的"1"是第k位
            一定存在ai的第k位是1，且ai^x < ai
            则将当前所有第k位是"1"的ai异或x
            一定可以使所有ai异或结果为0
        }
        则如果异或结果初始不为0，可以经过处理变为0
        所以异或结果=0先手必败，否则先手必胜(下一次给对手的结果为异或结果为0)

* 本题:
    left[i][j]表示我在[i,j]这个区间的左边放上一堆数量是多少的石头能够让我先手必败.
    right[i][j]表示我在[i,j]区间的右边放上一堆数量是多少的石头能让我先手必败.

    left[i][j]的性质:必然存在且唯一.

    对于给定的[i,j]区间,我们定义X = a[j], L=left[i][j-1],R= right[i][j-1],
    即在 [i,j-1]区间的左边放L先手必败,在右边放R先手必败
    * Case 1: R=x, left[i][j]=0
        因为X=R的时候[i,j]已经先手必败,左边就不用放了
    * Case 2: X < R && X < L, left[i][j] = X
        后手拿先手同样数量的石子，使先手先拿掉一侧最后一颗石子，后手存在另一侧的非必败(必胜区间，因为唯一)
    * Case 3: R < X <= L, left[i][j] = X-1
        (1)先手取右侧，取完=R,后手取完左侧
                      取完>R,后手保证左=右-1
                      取完<R,后手使左=右，跳转情况2
        (2)先手取左侧，取完>=R,后手保证左=右-1
                      取完<R,后手使左=右，跳转情况2
    * Case 4: L < X <= R, left[i][j] = X+1
        (1)先手取左侧，取完=L,后手取完右侧
                      取完>L,后手保证左=右+1
                      取完<L,后手使左=右，跳转情况2
        (2)先手取右侧，取完>=L,后手保证左=右+1
                      取完<L,后手使左=右，跳转情况2
    * Case 5: X > L && X > R, left[i][j] = X
        后手确保左=右
           
*/
#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")


#include <iostream>
using namespace std;

const int N = 1010;
int a[N], l[N][N], r[N][N];

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt", "r", stdin);
    #else
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        for(int len = 1; len <= n; len++)
            for(int i = 1; i + len - 1 <= n; i++)
            {
                int j = i + len - 1;
                if(len == 1) l[i][j] = r[i][j] = a[i];
                else {
                    int L = l[i][j-1], R = r[i][j-1], X = a[j];

                    //先手左侧必败
                    if(R == X) l[i][j] = 0;
                    else if (X<R && X<L || X>R && X>L) l[i][j] = X;
                    else if(R<L) l[i][j] = X-1;
                    else l[i][j] = X+1;

                    L = l[i-1][j], R = r[i-1][j], X=a[i];

                    //先手右侧必败
                    if(L==X) r[i][j] = 0;
                    else if (X<R && X<L || X>R && X>L) r[i][j] = X;
                    else if(L<R) r[i][j] = X-1;
                    else r[i][j] = X+1;
                }
            }
        if(n==1) puts("1");
        else printf("%d\n", l[2][n] != a[1]);
    }
    return 0;
}